package com.example.algorithms.sum;

/**
 * @Author Zhang Jie
 * @Date 10/15/20
 * @Version 1.0
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给一个整型数组，从数组中找出所有和为特定值的一对整数，输出它们的下标。
 * note:没有说是否有重复值
 */
public class TwoNumSum {

    /**
     * 假设数组中没有重复值
     *
     * @param sum
     */
    public static void find(int sum, int[] arr){
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            int surplus = sum-arr[i];
            if(map.containsKey(surplus)){
                System.out.printf("{%d,%d}",map.get(surplus),i);
            }
            map.put(arr[i],i);
        }
    }

    /**
     * 假设数组中有重复的值
     *
     * 1234568925
     */
    public static void findDuplicate(int sum, int[] arr){
       Map<Integer, Set<Integer>> map = new HashMap<>();
       for(int i =0;i<arr.length;i++){
           int surplus = sum-arr[i];
           if(map.containsKey(surplus)){
               Set<Integer> indexSet = map.get(surplus);
               for (Integer index : indexSet) {
                   System.out.printf("{%d,%d}\n",i,index);
               }
           }
           Set<Integer> currentSet;
           if(map.containsKey(arr[i])){
               currentSet = map.get(arr[i]);
           }else{
               currentSet = new HashSet<>();
               map.put(arr[i],currentSet);
           }
           currentSet.add(i);
       }
    }
}
